#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;


void process(vector<vector<int>>& visit,vector<vector<char>>& board, string word,int i,int j,int k,bool &find)
{
    if(i<0||i>=board.size()||j<0||j>=board[i].size())
    {
        return;
    }
    if(k==word.size())
    {
        find=true;
        return;
    }
    if(board[i][j]==word[k]&&visit[i][j]==0)
    {
        visit[i][j]=1;
        process(visit,board,word,i+1,j,k+1,find);
        process(visit,board,word,i-1,j,k+1,find);
        process(visit,board,word,i,j+1,k+1,find);
        process(visit,board,word,i,j-1,k+1,find);
        visit[i][j]=0;
    }else
        return;
}

bool exist(vector<vector<char>>& board, string word)
{
    bool result=false;
    int m=board.size();
    int n=board[0].size();
    bool find=false;
    vector<vector<int>> visit(m,vector<int>(n,0));
    for (int i = 0; i < board.size(); i++)
    {
        for (int j = 0; j < board[0].size(); j++)
        {
            if(board[i][j]==word[0])
            {
                
                process(visit,board,word,i,j,0,find);
                result=result||find;
            }
        }
        
    }
    return result;
    
}

int main()
{
    vector<vector<char>> board{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
    string word="ABCCED";
    cout <<boolalpha<<exist(board,word)<<endl;
}